# encoding:utf-8

import sys

r = 8
c = 8

s_init = [1, 1]

step_list = [s_init]
step_counts = r * c


def print_matrix(m):
    for i in range(len(m)):
        print('r{}: {}'.format(i + 1, m[i]))
    print('')


def find_next():
    rn = step_list[-1][0]
    cn = step_list[-1][1]
    # 顺时针查找
    if rn > 2 and cn < c and (not [rn - 2, cn + 1] in step_list):
        step_list.append([rn - 2, cn + 1])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn > 1 and cn < c - 1 and (not [rn - 1, cn + 2] in step_list):
        step_list.append([rn - 1, cn + 2])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn < r and cn < c - 1 and (not [rn + 1, cn + 2] in step_list):
        step_list.append([rn + 1, cn + 2])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn < r - 1 and cn < c and (not [rn + 2, cn + 1] in step_list):
        step_list.append([rn + 2, cn + 1])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn < r - 1 and cn > 1 and (not [rn + 2, cn - 1] in step_list):
        step_list.append([rn + 2, cn - 1])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn < r and cn > 2 and (not [rn + 1, cn - 2] in step_list):
        step_list.append([rn + 1, cn - 2])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn > 1 and cn > 2 and (not [rn - 1, cn - 2] in step_list):
        step_list.append([rn - 1, cn - 2])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)
    if rn > 2 and cn > 1 and (not [rn - 2, cn - 1] in step_list):
        step_list.append([rn - 2, cn - 1])
        if len(step_list) == step_counts:
            print_matrix(step_list)
            exit(0)
        find_next()
        step_list.pop(-1)

    pass


find_next()
